class Solution 
{
public:
    int tmp[50001];
    int reversePairs(vector<int>& nums) 
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }



    int mergeSort( vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return 0;

        int mid = (left + right) >> 1;
        int ret = 0;

        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        //先翻转
        int cur1 = left,cur2 = mid + 1, i = 0;
        //升序版本
        while(cur2 <= right)
        {
            while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2])
            {
                cur1++;
            }
            if(cur1 > mid)
                break;
            ret += mid - cur1 + 1;
            cur2++;
        }
        
        //降序版本
        // while(cur1 <= mid)
        // {
        //     while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
        //     {
        //         cur2++;
        //     }
        //     if(cur2 > right)
        //         break;
        //     ret += right - cur2 + 1;
        //     cur1++;
        // }


        cur1 = left,cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
            //    tmp[i++] = nums[cur2++]; //降序
                tmp[i++] = nums[cur1++];
            }
            else
            {
            //    tmp[i++] = nums[cur1++]; //降序
                tmp[i++] = nums[cur2++];
            }
        }

        while(cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right)
        {
            tmp[i++] = nums[cur2++];
        }

        for(int j = left; j <= right; j++)
        {
            nums[j] = tmp[j - left];
        }

        return ret;

    }
};
